#include <iostream>
#include <algorithm>
#include <map>
#include <iomanip>
#include <cstdlib>
#include "tinyxml.h"
#include "Graph.h"
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <map>

using namespace std;
#define NODE_CNT 50
class node
{
public:
	int number;
	node *next;
	node(int a, node *b)
	{
		number = a;
		next = b;
	}
};

class stacks
{
public:
	node *top;
	stacks(node *a = NULL)
	{
		top = NULL;
	}
	void push(int a)
	{
		if (top == NULL)
			top = new node(a, NULL);
		else
			top = new node(a, top);
	}
	void pop()
	{
		node *b = top;
		top = top->next;
		delete b;
	}

}; //保存已加入路径结点的栈

int cur_node;			  //当前结点，即为栈顶的结点
int next_node = NODE_CNT; //当前结点的下一个邻接点，即刚从栈顶弹出的结点，初始化为8
map<int, int> map_next;	  //每个结点的下一个邻接点，即刚从栈顶弹出的结点
int start = 0;
int endpoint = NODE_CNT - 1; //起点为0，终点 NODE_CNT-1
stacks aray[NODE_CNT] = {stacks(NULL)};
stacks stack(NULL);
int states[NODE_CNT];  //保存结点状态的数组
node *neighbour(int a) //,int b
{
	node *abc = aray[a].top;
	while ((NULL != abc)) //结点abc不空
	{
		if (states[abc->number] == 1) //已经在栈stack里了
		{
			abc = abc->next;
		}
		else //不在栈stack里
		{
			if (-1 == map_next[a]) //就要abc作为返回值
			{
				while (NULL != abc && states[abc->number] == 1)
				{
					abc = abc->next;
				}
				return abc;
			}
			else if (abc->number == map_next[a])
			{
				abc = abc->next;
				while (NULL != abc && states[abc->number] == 1)
				{
					abc = abc->next;
				}
				return abc; //将abc的下一个结点返回
			}
			else
			{
				abc = abc->next;
			}
		}
	}
	return NULL;
}

void edge2STATIC(map<string, Edge> &edges)
{
	for (auto &it : edges)
	{
		Edge e = it.second;
		e.str2int();
		aray[e.start].push(e.end);
		// cout<<"e.start "<<e.start <<"e.end"<<e.end<<endl;
	}
}

#include <ctime>

int main()
{
	clock_t startTime, endTime;
	startTime = clock(); //计时开始
	//初始化map_next
	for (int i = 0; i < NODE_CNT; i++)
	{
		map_next[i] = -1;
	}

	Graph graph;
	int nodeNum = 0;
	int edgeNum = 0;

	readXml("map_node50_v1.1.xml", graph.nodes, graph.edges, nodeNum, edgeNum);

	edge2STATIC(graph.edges);

	node *neighbour(int a); // ,int b
	stack.push(start);		//将起点入栈
	states[start] = 1;		//将起点标记为入栈状态

	while (NULL != stack.top) //栈不为空
	{
		if (stack.top->number == endpoint)
		{
			node *abc = stack.top;
			//vector<Node> path;
			_Path path;
			while (abc->number != start)
			{
				string strstart = "s" + to_string(abc->number);
				//cout << strstart << ",";
				abc = abc->next;
				path.nodes.push_back(graph.nodes[strstart]);
				string strend = "s" + to_string(abc->number);
			}
			path.nodes.push_back(graph.nodes["s0"]);
			stack.pop();		  //将栈顶结点弹出
			states[endpoint] = 0; //清除终点的状态
			map_next[endpoint] = -1;
			graph.paths.push_back(path);
		}
		else
		{
			cur_node = stack.top->number;
			if (neighbour(cur_node) != NULL) //邻居不为空
			{
				node *d = neighbour(cur_node);
				map_next[cur_node] = d->number;
				cur_node = d->number;
				stack.push(cur_node);
				states[cur_node] = 1;
			}
			else
			{
				stack.pop();
				states[cur_node] = 0;
				map_next[cur_node] = -1;
			}
		}
	}
	graph.calTimeDistance();
	graph.minDistanceSort();

	for (int i = 0; i < 3; i++)
	{
		graph.paths[i].print();
	}
	graph.minTimeSort();

	for (int i = 0; i < 3; i++)
	{
		graph.paths[i].print();
	}
	cout << "路径条数：" << graph.paths.size() << endl;

	graph.calChognhe(&graph.paths[0], &graph.paths[1]);
	endTime = clock(); //计时结束
	cout << "The run time is: " << (double)(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;
	return 0;
}
